Not applicable.
Not applicable.
This invention is in the field of data communications, and is more specifically directed to coding techniques for high data rate transmissions via cable modems.
In the field of data communications, particularly in the provision of Internet access to homes, the use of the cable television (CATV) network as the medium of communication has become attractive. The attractive features of the CATV network include the relatively large installed base of homes having cable television service, and also the inherently high data rates that may be carried by the coaxial cable with which cable television programs are delivered, especially when compared with twisted-pair copper wiring commonly used in telephone service. As such, significant effort has been undertaken to develop the appropriate technology for two-way broadband communication over the CATV network. Attention is directed, in this regard, to Perkins and Gatherer, xe2x80x9cTwo-way broadband CATV-HFC networks: state-of-the-art and future trendsxe2x80x9d, Computer Networks, Vol. 31 (Elsevier Science B.V., 1999), pp. 313-326, for a survey of the current state of technology in this field.
An important measure of any high-data-rate communications approach is referred to as xe2x80x9cspectral densityxe2x80x9d, or synonymously as xe2x80x9cspectral efficiencyxe2x80x9d. Spectral density refers to the number of bits that may be communicated per second for a given frequency. Of course, the higher the spectral density, the more information that can be communicated at the transmission frequency. In recent -years, relatively complex modulation techniques have been developed to improve the spectral density of data communications. It is now commonplace for communications to be carried out using phase and amplitude modulation, in combination, to modulate digital data into the transmitted signal. As is fundamental in such modulation, a xe2x80x9cconstellationxe2x80x9d is defined by a number of discrete points in complex Euclidean space, each point representative of a value of a data symbol. An example of a complex modern constellation, referred to in the art as 256 QAM, has 256 points mapped into a sixteen-by-sixteen array in complex space; this constellation thus. permits the transmission of eight-bit symbols, and provides excellent spectral density.
As is also well-known in the art, the spectral density of a transmission scheme is limited by the noise in the transmission channel. If the noise is excessive, constellation points may be mistaken for one another, resulting in. an error in the transmission. As spectral density increases (i.e., with more points in the complex space constellation), the distance between adjacent constellation points decreases; for a given level of noise, a smaller distance between adjacent points directly relates to the likelihood of a transmission error.
Redundant encoding techniques have been used in combination with phase and amplitude modulation to ease the tradeoff between spectral density and error rates. One encoding technique is referred to as xe2x80x9ctrellisxe2x80x9d coding, which is a species of convolutional encoding. A survey of trellis coding is described in Ungerboeck, xe2x80x9cTrellis-Coded Modulation with Redundant Signal Sets Part I: Introductionxe2x80x9d, IEEE Communications Magazine, Vol. 25, No. 2 (1987), pp. 5-11. According to trellis coding techniques, the constellation is divided into subsets, but the signal transitions are limited by way of a finite state machine. In this way, depending upon the particular implementation, transitions are not permitted to neighboring points in the constellation in every state, while transitions from state to state are permitted so that all points in the available constellation are used with equal frequency. The use of the finite state machine thus includes the value of prior symbols into the determination of the output signal, providing controlled redundancy in the encoding scheme. In trellis coding, only a portion of the bits of the symbol are encoded while the remaining symbol bits are transmitted in an uncoded fashion. The coded bits select the constellation subset to which the symbol relates, while the uncoded bits indicate the particular point within the selected constellation subset corresponding to the symbol. Because of the subdivision of the constellation, however, the Euclidean distance between the uncoded bits is increased. In other words, for a given bit error rate, the signal-to-noise ratio required using trellis coding may be a few dB less than for the uncoded case.
By way of further background, U.S. Pat. No. 5,511,082 describes a method and apparatus for encoding digital data using a convolutional code to encode part of the transmitted symbols. The convolutional code in this example has a coding rate of 4/5, which indicates that one redundant bit is inserted for every four symbol bits to be encoded. An extension of this approach is used in the trellis coding specified for cable modems according to ITU-T Recommendation J.83 Annex B, and in other cable modems specifications. In this approach, four constellation subsets are used, with the two least significant bits being coded according to a convolutional code, with the coded result used to select among the constellation subsets. FIG. 1 illustrates an example of this methodology, as utilized in a simple 16-QAM context. As evident from FIG. 1, the least significant bit of the codeword alternates along the imaginary axis of the constellation, and the second least significant bit alternates along the real axis. Considering the two LSBs to indicate the selection of the sub-constellation (e.g., all points xx01 correspond to one sub-constellation or subset), it is evident from FIG. 1 that adjacent points within a sub-constellation are significantly separated from one another than are adjacent points in the overall 16-QAM constellation. In this example, this approach doubles the Euclidean distance between adjacent uncoded constellation bits (providing a 6 dB improvement in error performance).
FIG. 2 illustrates, in block diagram form, the coder functions used to implement this LSB encoding approach described in U.S. Pat. No. 5,511,082. Parser 3 receives a bitstream B, and parses the incoming bitstream B into m-bit symbols, considering the coding. In this example, where 4/5 convolutional coders 5I and 5Q are used, five m-bit symbols are to be generated at a time; as such, parser 3 forwards 5(mxe2x88x922) bits in uncoded fashion to QAM map function 7. Parser 3 also forwards four bits to 4/5 convolutional coder 5I, and four bits to 4/5 convolutional coder 5Q.
FIG. 3 illustrates the functional construction of one of 4/5 convolutional coders 5I and 5Q which, of course, are similarly constructed. As shown in FIG. 3, four input bits x0 through x3 are serially presented (bit x3 being earliest in time, and bit x0 latest) to convolutional coder 5. Convolutional coder 5 includes four delay stages S0 through S3, the outputs of which are applied to exclusive-OR functions 90 and 91 according to the desired encoding. In this example, exclusive-OR function 90 receives the outputs of all four delay stages S0 through S3 and also the currently applied input bit, and exclusive-OR function 91 receives the currently applied input bit, and the outputs of delay stages S1 and S3. As described in the above-referenced U.S. Pat. No. 5,511,082, this arrangement corresponds to octal generators of 258 (101012) and 378 (111112), for exclusive-OR functions 90 and 91, respectively.
The outputs of exclusive-OR functions 9 are applied to puncture logic 11, which selects the bits to be output by coder 5 according to the desired puncture scheme. In this example, puncture logic 11 selects each of the four bits output by exclusive-OR function 90 from the sequence of four input bits x0 through x3, and only the fourth (last) bit output by exclusive-OR function 91. As described in the above-referenced U.S. Pat. No. 5,511,082, a puncture map is described for this arrangement as:   {                    1                    0                    0                    0                            1                    1                    1                    1              }
The five output bits from puncture logic 11 are illustrated, in FIG. 3, as bits O0 through O4. In this arrangement, output bits O0 through O3 are derived in sequential order (bit O0 being earliest in time) by exclusive-OR function 90, and output bit O4 is derived by exclusive-OR function 91 (at a time coincident with bit O3 from exclusive-OR function 90).
One may readily derive the output bits O from the construction of coder 5. In this example, where the initial state of coder 5 is represented by the outputs of delay stages S0 through S3, output bits O0 through O4 correspond to the following logical exclusive-OR operations:
O0=x3⊕S0⊕S1⊕S2⊕S3
O1=x2⊕x3⊕S0⊕S1⊕S2
O2=x1⊕x2⊕x3⊕S0⊕S1
O3=x0⊕x1⊕x2⊕x3⊕S0
O4=x3⊕S0⊕S1⊕S2⊕S3
One may readily derive a state table for coder 5 according to this conventional construction.
The improvement in error reduction provided by this conventional coding approach may be analyzed by determining the extent to which the Euclidean distance is increased between adjacent points in the same sub-constellation (uncoded bit error), and also the Euclidean distance between the sub-constellations themselves (coded bit error or, conversely, coding gain). In effect, one may consider the error reduction (or gain) by identifying the smallest Euclidean distance of each of these two error types.
For the uncoded bits, considering d as the Euclidean distance between adjacent points in the overall constellation (i.e., union of all four sub-constellations), analysis of this conventional 4/5 convolutional coding approach of FIGS. 2 and 3 has shown, according to the present invention, that the closest two uncoded points (i.e., those communicated directly to QAM map function 7 in FIG. 2) are separated by Euclidean distance 2d.
For the coded bits, the analysis considers the Euclidean distance of errors that occur along a xe2x80x9cpathxe2x80x9d (in the Viterbi decoding sense) in such a manner as to be not detected. Because the 4/5 convolutional code is linear, the error may be analyzed relative to any state; for convenience, the analysis described herein will correspond to erroneous departure from and return to state 0000 (S3 through S0). As noted above, in the conventional approach of FIGS. 2 and 3, the least significant bits are coded, such bits being separated by Euclidean distance d in the constellation. Accordingly, for a minimum number of errors necessary to depart and return to a given state, commonly referred to as the minimum Hamming distance dfree (or xe2x80x9cfree Hamming distancexe2x80x9d), the square of the coded Euclidean distance is xe2x89xa7dfreed2.
As noted above, because the overall error improvement corresponds to the smaller of the Euclidean distances of the coded and uncoded portions of the communicated bits, the coding performance will correspond to the smaller of 22d2 (the square of the Euclidean distance for the uncoded bits) and dfreed2 (the square of the coded Euclidean distance). Accordingly, if the minimum number of errors in the LSBs that can cause an undetected error (i.e., the minimum Hamming distance dfree) is less than four, the convolutional coding will limit the overall trellis coding performance.
It has been found, according to the present invention, that this conventional trellis coding approach of FIGS. 2 and 3 is indeed limited by the 4/5 convolutional coding. Analyzing state 0000, it is observed that the output bits O contain at least two bits at a xe2x80x9c1xe2x80x9d level. As such, the Hamming distance H upon leaving state 0000 is  greater than 1. Conversely, it is observed that no all zero outputs are present upon entering state 0000, and as such the Hamming distance H upon entering state 0000 is xe2x89xa71. The total distance involved in leaving and returning to state 0000 is thus greater than two; it can be readily derived by those in the art, having reference to this description, that the minimum Hamming distance dfree according to this conventional 4/5 convolutional coding is three (i.e., dfree=3).
One may consider the coding xe2x80x9cgainxe2x80x9d by analysis of the number of transmitted bits in the transmitted constellation. The power in an m-bit pulse-amplitude modulated (PAM) constellation, for the case where the Euclidean distance d=2 (i.e., where the available PAM points correspond to xc2x11, xc2x13, xc2x15, . . . ), is:             2              2        ⁢        m              -    1    3
In the conventional arrangement of FIGS. 2 and 3, one may readily see that 5 m-bit symbols are transmitted by QAM map function 7, in place of the 4 m-bit symbols plus one mxe2x88x921 bit symbol that would have been sent without coding (i.e., the number of bits parsed by parser function 3 is 4m+(mxe2x88x921)). In other words, the coding arrangement inserts one additional bit in its constellation. One may derive the power increase required as a result of this additional constellation bit as the ratio of the coded PAM power to the uncoded PAM power as follows:             5      ⁢                                    2                          2              ⁢              m                                -          1                3                            4        ⁢                                            2                              2                ⁢                m                                      -            1                    3                    +                                    2                          2              ⁢                              (                                  m                  -                  1                                )                                              -          1                3              =                    5                  4          +                                                    2                                  2                  ⁢                                      (                                          m                      -                      1                                        )                                                              -              1                                                      2                                  2                  ⁢                  m                                            -              1                                          ≈              5                  4          +                      1            4                                =          20      17      
In order to maintain the transmission power within the specified power constraint, this power increase necessitates a reduction in the effective coding gain. For the example where the coding gain is 3 (or 10 log10 3 dB), the effective coding gain provided by this conventional 4/5 convolutional LSB coding scheme is reduced to 4.07 dB (i.e., 10 log10 3-10 log10 (20/17)), which is less than the 6 dB improvement that this approach provides the uncoded bits. As such, it has been observed, according to the present invention, that the performance of the technique described in U.S. Pat. No. 5,511,082 is limited by its convolutional coding gain.
By way of further background, it is known that the performance of a trellis-coded modulation implementation may be improved by increasing the number of trellis states in the coding, until the minimum squared Euclidean distance (MSED) between valid sequences of subsets of the constellation exceeds the MSED within a constellation subset. Attention is directed, in this regard, to Wei, xe2x80x9cTwo-Level Coding Based on Trellis-Coded Modulation and Reed-Solomon Codesxe2x80x9d, IEEE Trans. on Communications, Vol. 42, No. 12 (December, 1994), pp. 3098-3108. However, the sixteen-state trellis coding approach described in U.S. Pat. No. 5,511,082 has been adopted by the International Telecommunications Union (ITU), as Annex B of proposed designation J.83. It has been heretofore believed in the art that additional coding gain is not available from increasing the number of states in the convolutional coding implementation according to this approach.
By way of further background, Yosuda et al., xe2x80x9cHigh Rate Punctured Convolutional Codes for Soft Decision Viterbi Decodingxe2x80x9d, Trans. on Communications, Vol. COM-32, No. 3 (IEEE, March 1984), pp. 315-318, provides a table of punctured codes, including rates and minimum Hamming distances dfree for these codes. As evident therein, a convolutional code of 4/5 code rate exists which has a dfree of 4, thus providing a coding gain of 5.31 dB (following the above analysis).
It is therefore an object of the present invention to provide improved coding gain in the convolutional coding of communicated data.
It is a further object of the present invention to provide a telecommunications system, modems therein, and methods of operating the same, that provide such improved coding gain.
It is a further object of the present invention to provide such a system, modems, and methods in which the improved convolutional coding may be implemented with little cost.
It is a further object of the present invention to provide such benefits that are particularly well-suited for cable modem communications.
Other objects and advantages of the present invention will be apparent to those of ordinary skill in the art having reference to the following specification together with its drawings.
The present invention may be implemented into the convolutional coding of data to be transmitted and received over a communications network, such as between modems communicating data over coaxial cable or another high-speed medium. According to the present invention, modems in the communication network operate according to a convolutional coding scheme having thirty-two or sixty-four states, with a Hamming distance in each case of four. These coding schemes provide sufficient coding gain to exceed the Euclidean distance within the constellation subsets, and are also backward-compatible with conventional coding schemes.